// 给你一个字符串 s，找到 s 中最长的回文子串。
/**
 * @param {string} s
 * @return {string}
 */
//方法一：  baoli    时间复杂度O(n^2) 空间复杂度O(n^2)
// var longestPalindrome = function(s) {
//     let max = 0;
//     let maxStr = '';
//     for (let i = 0; i < s.length; i++) {  //遍历字符串
//         for (let j = i; j < s.length; j++) {  //从i开始，到最后一个字符
//             let str = s.slice(i, j + 1);  // 截取字符串
//             if (isPalindrome(str) && str.length > max) {  // 判断是否是回文串
//                 max = str.length; // 更新最大长度
//                 maxStr = str; // 更新最大回文串
//             }
//         }
//     }
//     return maxStr;  // 返回最大回文串
// };
// function isPalindrome(str) {
//     let left = 0;   // 左指针
//     let right = str.length - 1;   // 右指针
//     while (left < right) {   // 左右指针不相等
//         if (str[left] !== str[right]) {  // 如果不相等，返回false
//             return false;   // 返回false
//         }
//         left++;  // 左指针右移
//         right--;  // 右指针左移
//     }
//     return true;
// }
//方法二
// var longestPalindrome = function(s) {
//     let max = 0;
//     let maxStr = '';
//     for (let i = 0; i < s.length; i++) {  //遍历字符串
//         let str = helper(s, i, i);  // 截取字符串
//         if (str.length > max) {  // 判断是否是回文串
//             max = str.length; // 更新最大长度
//             maxStr = str; // 更新最大回文串
//         }
//         str = helper(s, i, i + 1);  // 截取字符串
//         if (str.length > max) { // 判断是否是回文串
//             max = str.length;
//             maxStr = str;
//         }
//     }
//     return maxStr;
// };
// function helper(s, left, right) {
//     while (left >= 0 && right < s.length && s[left] === s[right]) {
//         left--;
//         right++;
//     }
//     return s.slice(left + 1, right);
// }
//动态规划解法longestPalindrome
// var longestPalindrome = function(s) {
//     let max = 0;
//     let maxStr = '';
//     let dp = [];
//     for (let i = 0; i < s.length; i++) {
//         dp[i] = [];
//         for (let j = 0; j < s.length; j++) {
//             dp[i][j] = false;
//         }
//     }
//     for (let i = 0; i < s.length; i++) {
//         dp[i][i] = true;
//         if (i < s.length - 1 && s[i] === s[i + 1]) {
//             dp[i][i + 1] = true;
//             max = 2;
//             maxStr = s.slice(i, i + 2);
//         }
//     }
//     for (let len = 3; len <= s.length; len++) {
//         for (let i = 0; i < s.length - len + 1; i++) {
//             let j = i + len - 1;
//             if (s[i] === s[j] && dp[i + 1][j - 1]) {
//                 dp[i][j] = true;
//                 if (len > max) {
//                     max = len;
//                     maxStr = s.slice(i, j + 1);
//                 }
//             }
//         }
//     }
//     return maxStr;
// };

// const countSubstrings = (s) => {
//     const strLen = s.length;
//     let numOfPalindromicStr = 0;
//     let dp = Array.from(Array(strLen), //Array.from
//         () => Array(strLen).fill(false)); // 创建一个二维数组
//     for(let j = 0; j < strLen; j++) {
//         for(let i = 0; i <= j; i++) {
//             if(s[i] === s[j]) {
//                 if((j - i) < 2) {
//                     dp[i][j] = true;  // 如果是回文串，则dp[i][j] = true
//                 } else {
//                     dp[i][j] = dp[i+1][j-1];  // 如果是回文串，则dp[i][j] = dp[i+1][j-1]
//                 }
//                 numOfPalindromicStr += dp[i][j] ? 1 : 0;
//             }
//         }
//     }
//
//     return numOfPalindromicStr;
// }

// const longestPalindromeSubseq = (s) => {
//   const strLen = s.length;
//   let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));
//
//   for(let i = 0; i < strLen; i++) {
//     dp[i][i] = 1;
//   }
//
//   for(let i = strLen - 1; i >= 0; i--) {
//     for(let j = i + 1; j < strLen; j++) {
//       if(s[i] === s[j]) {
//         dp[i][j] = dp[i+1][j-1] + 2;
//       } else {
//         dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
//       }
//     }
//   }
//
//   return dp[0][strLen - 1];
// };


// var longestPalindrome = function(s) {
//     let max = 0;
//     let maxStr = '';
//     for (let i = 0; i < s.length; i++) {  //遍历字符串
//         for (let j = i; j < s.length; j++) {  //从i开始，到最后一个字符
//             let str = s.slice(i, j + 1);  // 截取字符串
//             if (isPalindrome(str) && str.length > max) {  // 判断是否是回文串
//                 max = str.length; // 更新最大长度
//                 maxStr = str; // 更新最大回文串
//             }
//         }
//     }
//     return maxStr;  // 返回最大回文串
// };
// function isPalindrome(str) {
//     let left = 0;   // 左指针
//     let right = str.length - 1;   // 右指针
//     while (left < right) {   // 左右指针不相等
//         if (str[left] !== str[right]) {  // 如果不相等，返回false
//             return false;   // 返回false
//         }
//         left++;  // 左指针右移
//         right--;  // 右指针左移
//     }
//     return true;
// }
var longestPalindrome=function (s) {
    let max = 0;
    let maxStr = '';
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            let str = s.slice(i, j + 1);
            if (isPalindrome(str) && str.length> max) {
                max = str.length; // 更新最大长度
                maxStr = str;
            }
        }
    }
    return maxStr;
}
function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    while (left < right) {
        if (str[left] !== str[right]) {
            return false;   //
        }
        left++;
        right--;
    }
    return true;
}

console.log(longestPalindrome('babad'));
// console.log(countSubstrings('babad'));
// console.log(longestPalindromeSubseq('bbbab'));